1. Field of the Invention
The invention relates to methods of loading or storing rectangular objects in rectangular areas or spaces of transportation or storage containers.
2. Background and Prior Art
The determination of the most favorable area division in cutting essentially rectangular objects out of a sheet or plate of material, such as leather or metal, and also the positioning of objects in a space, such as the positioning of postal packages in a container used by the post office, and the positioning of containers having different dimensions in a cargo space of, for example, a ship has hitherto been done mainly by hand, with a member of staff attempting to achieve an optimum material utilisation or packing density on the basis of his experience. It will be clear that it is desirable to at least partially automate this cutting or packing, in particular if it is to be accompanied by a reduction in the material loss or an increase in the packing density, respectively, that is to say a more optimum use of the available material or the available space.
A problem in this connection is that the calculation of the free subareas on an area partially filled with objects or free spaces in a space partially filled with objects is very complex, in particular if the objects already positioned have different dimensions.
The same problem zpplies to the calculation of an optimal selection of a next object from a number of objects to be placed with given dimensions for placing it in one of the calculated free subareas or subspaces in order to reach optimal use of the momentaneously available free area or space. For example for the three-dimensional case it is known that an automated parcel handling as known from S.P. Lie, "Automated parcel handling with an industrial robot", Proceedings of the Institution of Mechanical Engineers, 13-14 May 1986, Birdcage Walk, London, pp. 183-187) needs a loading algorithm with the task to determine which one of a number of buffered parcels must be handled next, and how this parcel can be placed in a container in the best possible way in order to achieve efficient loading of the container. This known algorithm uses a datastructure representing the space already occupied int he container by parcels, which datastructure is ot described in further details. Likewise it is not described how a next parcel is selected and placed in the free space for achieving optimal use thereof. H. Gehring et al., " A computer-based heuristic for packing pooled shipment containers", European Journal of Operational Research 44(1990), pp. 227-288, disclose a method for the generation of stowage plants for the packing of boxes entered in a list with decreasing volume in a container. The packing occures in vertical layers. The first box to be filled in the layer is defined as a layer determining box, whereas the spare spaces of the layer are filled each time with the best fitting pairs of boxes remaining in the list, i.e. the pair with the highest volume which can be fitted in the apare space. Alternative stowage plans are produced by different positions of the layer determining box or by moving the second, third, etc. element of the box-list to the beginning of the list before starting the method for generation. From the different stowage plans a stowage overseer can choose a suitable plan. This known method has some drawbacks, e.g. that only within each layer a certain optimisation of the packing density can be reached and that is needs human intervention for selecting a suitable one from the different generated stowage plans. In addition, the calculations are always to be carried out again after positioning a new object.